% Chapter X

\chapter{Introduction} % Chapter title
\label{ch:intro} % For referencing the chapter elsewhere, use \autoref{ch:name} 

In nature, many animals societies exhibit forms of collective behavior.
Such kind of behavior emerges from interactions occurring at animal level.
One of the reasons for those interactions is that agents are often faced with demanding activities, whose complexity is generally beyond the capabilities of the individual.
Hence, the only way to perform such kind of tasks is to require the intervention of other entities and join forces with them.
When cooperation is triggered, the problem of dividing the global duty into more, simpler components and assign (\ie  allocate) them to the different agents arises.

Indeed, \emph{task allocation} is a common problem that can be observed in different collaborative societies. 
The way the allocation is performed, however, varies across different species.

\graffito{The division of labour process in human societies has raised many philosophical and sociological issues, discussed by Plato, Adam Smith and Karl Marx, among others, whose discussion is beyond the scope of this thesis.}
In humans, the most prominent example of this problem is the \emph{division of labour}.
This process consists of the decomposition a work activity into sub-tasks and their \emph{allocation} to different individuals, in order to profit of the skills and capabilities possessed by each of them.
The \emph{allocation} is generally performed in a centralized manner, with a single entity that assign tasks and/or determine the degree of specialization of each agent. 
The presence of such entity, with a global knowledge of the agents and the tasks, allows, in most cases, for a quick and coherent allocation.
However, a similar approach has some major drawbacks.
First of all, the presence of a single unit with enhanced capabilities, introduces a single potential point of failure in the system. In fact, the allocation, thus the possibility to work of all the other agents depends on the "allocator".
As soon as it will be unable to perform the allocation, the whole system will stop functioning.
Furthermore, in many contexts it is impossible or impractical to gather a global knowledge of the system, hence limiting the effectiveness of the centralized solution.

Surprisingly, successful examples of task allocation and task partitioning can be found in the animal kingdom.
For instance, eusocial organisms (mostly insects, with some exceptions) are characterized by a reproductive division of labour, a specialization among reproductive and non-reproductive activities (caring for other individuals, nest building and defense, among others) that occurs at insect level.
Moreover, some species of ants and bees are able to respond to changes in demand for particular activities by redistributing the available workforce.
Here, task allocation is a product of the cooperation  or, in other words, a consequence of the \emph{self-organization} of the individuals. 
Even though each agent is a relatively simple entity, with limited sensing capabilities, the task allocation for the complex activity can be achieved through processes and interactions locally occurring among them.
 
The study of collective behavior of decentralized, self-organized systems, natural or artificial, composed by a relevant number of homogeneous organisms, is the main focus of the of \emph{\acl{SI}}, a research sub-field in \ac{AI}.
The goal of this research is to formulate models to explain the emergence of the behavior in order to be able to design effective, distributed algorithms for problem solving.
%\acl{SR} tries to go even further, by applying this paradigm to multi-robot systems.
In this thesis, we apply this paradigm to the \emph{task allocation} problem.
To be more precise, we focus on the problem of allocating agents to \emph{spatially distributed} tasks.

Our study will be performed in the framework of \acl{SR}, hence the agents will be a group of simple and (quasi) identical robots, with decentralized control and lack of synchronicity \citep{beni2005swarm}.
Given their characteristics, we decided to adopt is the \nameref{subsec:epuck}, a small mobile robot, as the robotic platform for our experience.
Tasks, on the other hand, are represented by \nameref{subsec:TAM}s, devices specifically designed to allow the \emph{e-puck} to abstract tasks that are beyond its capability.

In our implementation of the problem, tasks are arranged to form a limited number of clusters in space.

Our purpose is to understand whether it is possible to achieve a uniform allocation of the robots across the clusters by relying only on \emph{\acl{SO}}, without the need for any centralized solution.

In order to do so, we developed three methods.
The first one (\emph{Naive}) consists simply of a greedy allocation of the robots, as soon as the tasks are discovered, while the second one (\emph{Probabilistic}) introduces a probabilistic mechanism to better distribute the robots across different clusters.
The third (\emph{Informed}) is built by adding an odometry-based memory of the last visited cluster to the \emph{Probabilistic} one.

The performance of these methods are compared on three different scenarios: \nameref{subsec:A}, \nameref{subsec:B}, \nameref{subsec:C}, each one of them characterized by a precise disposition in space of the clusters and the initial deployment area of the robots. 

%----------------------------------------------------------------------------------------

\section*{Thesis Layout}
The thesis is structured in 5 chapters.

In \nameref{ch:backandrelwork} we start by presenting the reader the relevant notions related to the \ac{SI} field.
Then, we discuss the problem of \emph{spatial allocation} and we provide a summary of state-of-the-art on the  problem (\nameref{sec:sa}).
We conclude the chapter by providing the readers some specifics concerning the hardware (\nameref{subsec:epuck}, \nameref{subsec:TAM}) and software (\nameref{subsec:ARGoS}) components used in the development of the thesis.

In \nameref{ch:meth}, we first provide a formal \nameref{sec:probstat}, we describe our \nameref{sec:exsetup} and we illustrate the three developed methods, the \nameref{subsec:naive}, \nameref{subsec:prob} and \nameref{subsec:inf} one. 

The chapter \nameref{ch:results} is dedicated to a detailed analysis of the results and properties of the methods.  
First, we present the scenarios (Section \ref{sec:scenario}) that we used to test our methods and the \nameref{sec:metrics} we measured in our experiments.
Then, we focus on two relevant properties of our methods: the \emph{uniformity} of the \emph{speed} of the allocation, analyzed respectively in Sections \ref{sec:allocunif} and \ref{sec:allocatime}.
The chapter is concluded by an evaluation of the difficulty of the different scenarios (Section \ref{sec:diff}). 

Finally, \nameref{ch:conclandfutwrk} concludes the thesis with a discussion on the obtained results and suggestions for future research directions to explore.



%------------------------------------------------The objective of the Master's thesis is to develop a method to allocate robots to dynamic and spatially distributed tasks.

